// 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
// candidates 中的每个数字在每个组合中只能使用 一次 。
//
// 注意：解集不能包含重复的组合。
//
//
//
// 示例 1:
//
//
// 输入: candidates = [10,1,2,7,6,1,5], target = 8,
// 输出:
// [
// [1,1,6],
// [1,2,5],
// [1,7],
// [2,6]
// ]
//
// 示例 2:
//
//
// 输入: candidates = [2,5,2,1,2], target = 5,
// 输出:
// [
// [1,2,2],
// [5]
// ]
//
//
//
// 提示:
//
//
// 1 <= candidates.length <= 100
// 1 <= candidates[i] <= 50
// 1 <= target <= 30
//
//
// Related Topics 数组 回溯 👍 1139 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

// Java：组合总和 II
public class P40CombinationSumIi {
    public static void main(String[] args) {
        Solution solution = new P40CombinationSumIi().new Solution();
        // TO TEST
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> listList = solution.combinationSum2(candidates, target);
        System.out.println(listList);
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            // 为了将重复的数字都放到一起，所以先进行排序
            Arrays.sort(candidates);
            this.combinationSum2(target, 0, 0, candidates);
            return this.result;
        }

        private void combinationSum2(int target, int curSum, int index, int[] candidates) {
            if (curSum == target) {
                this.result.add(new ArrayList<>(this.path));
                return;
            }

            for (int i = index; i < candidates.length && curSum + candidates[i] <= target; i++) {
                // 正确剔除重复解的办法
                // 跳过同一树层使用过的元素
                // 参考链接
                // https://gitee.com/programmercarl/leetcode-master/blob/master/problems/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.md
                if (i > index && candidates[i] == candidates[i - 1]) {
                    continue;
                }

                this.path.add(candidates[i]);
                curSum = curSum + candidates[i];
                //
                this.combinationSum2(target, curSum, i + 1, candidates);

                // 回溯
                this.path.removeLast();
                curSum = curSum - candidates[i];
            }
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

}
